package cn.com.forever.offer;

public class 删除并获得点数 {
    public static void main(String[] args) {
        int[] nums = {2,2,3,3,3,4};
        int[] nums2 = {1,1,1,2,4,5,5,5,6};
        //int[] res = deleteAndEarn(nums2);
        System.out.println(deleteAndEarn(nums2));
    }

    public static int deleteAndEarn(int[] nums) {
        int MaxNum = 0;
        for(int i:nums){
            MaxNum = i > MaxNum?i:MaxNum;
        }
        int[] sort = new int[MaxNum+1];
        for(int i:nums){
            sort[i]++;
        }
        int[] dp = new int[MaxNum+1];
        dp[0] = 0;
        dp[1] = sort[1];
        for (int i = 2; i < MaxNum+1; i++) {
            dp[i] = Math.max(dp[i-1],dp[i-2]+i*sort[i]);
        }
        return dp[MaxNum];
    }
}
